FIG. 1 depicts a typical process 10 in designing and constructing a computer system that uses queues. The first step is the architectural design phase 11, and this is where the developer formulates the specification of the system, and determines which components will be in the system, the number and characteristics of the FIFO queues (first-in, first-out), whether the system will use cache, etc. The specification can be written in a natural language like English or in a pseudo code like C.
In the second step 12, the specification is written in a high level description language (HDL). Here the specification from the design step 11 is written in code language like VERILOG or VHDL. After the code is written, the next step 13 is to perform software simulation or hardware emulation on the system design and HDL implementation. Software simulation is using software to simulate the performance of the system. Hardware emulation is using off-the-shelf hardware components to construct a model of the system. The developer may choose to use either simulation or emulation, or both.
The design of step 11 and the implementation of step 12 are tested, and if bugs are found in step 14, depending upon their origin, then either the design or the implementations will be modified. From the design flow 10, it is apparent that design errors are more serious than implementation errors. Steps 11-14 are iterated until no more bugs are found.
Once no more bugs are found by simulation and/or emulation, then the chip is developed. In step 15 the design is synthesized, and put on tape, and released to the foundry where the chip is produced. Once the chip is produced, the actual chip will be tested via post silicon verification. As compared with to step 13, where the system chip was either simulated via software or emulated via hardware, in step 16 the actual physical chip is tested for bugs. If bugs 18 are present, then the developer will determine whether the bugs can be fixed by a change in a metal layer, or whether the design must be modified in step 11 or the implementation must be changed in step 12. If the change can be made in the metal layer then the change is made in step 15 by sending the chip back to the foundry. However, if the error is more serious, then correction will take place in either step 11 or step 12.
A critical aspect to the design flow 10 is queue flow control. Typical designs will have many queues and FIFOs, rams, stacks, as well as other components. One way of considering FIFO queues is to regard entities placing entries into the queue as a producer, and entities removing entries from the queue as a consumer. The interaction of consumers and producers with the queue can cause two problems. One problem is queue overflow, where producers overload a queue, insert more data than the queue can store and data is lost or overwritten, which is sometimes terms `dropped on the floor`. The other problem is queue underflow. This condition occurs when consumers pull more data from the queue than the queue is holding, and consequently the consumers receive invalid data.
Queue flow control is traditionally addressed in steps 13 and/or 16, where verification is being performed. The traditional approach to verify queue flow-control has been through simulation, emulation, or post-silicon verification. In large systems, the simulation approach verifies few cases as it becomes very difficult to stress the queues enough to get to the corner cases. This is because the queues are deep in systems, and thus it takes many simulation cycles to get an entry into the queue. Consequently, it is difficult and costly to fill up the queue and verify the corner or worst case situations.
One prior art solution is to reduce the number of queue entries for the simulation. For example, suppose that the queue is designed to store 100 entries, but for the simulation, it will be assumed that the queue only has 10 entries. Thus, it is now possible for the simulation to more easily fill up the queue and test the corner cases. However, this assumption introduces two new problems. First the reduction in size may lead to errors that would not exist if the queue was at 100 entries, i.e. false positives. Second, the reduction in size may hide other errors, and allow bugs to slip through the verification, i.e. false negatives.
Although hardware emulation covers more cases than software simulation, it does not guarantee that all the cases have been verified in the various queues in the system. Since, real off-the-shelf hardware is being used to model the design, then the system is working at a much faster rate than software simulation. Thus, the queues are easier to fill up and the case coverage is going to be better than the software simulation. However, since the system is represented in a piecemeal fashion, it is difficult to isolate the true sources of any errors that may occur, as each error might have multiple sources. Moreover, the piecemeal fashion may introduce errors that would not be present in the actual chip, because of conditions in the emulation that would not be present in the actual chip, e.g. additional wire delay. Furthermore, since this is a representation of the design and not the actual chip, there is still incomplete coverage, and not all of worst cases are tested.
Using post-silicon verification overcomes most of the problems associated with software simulation and hardware emulation, since the actual chip is being tested and not some representation of the design. However, the main problem with verification is that it takes place late in the design flow or cycle, such that errors in the design, implementation, and/or realization may occur after the chip has been shipped to a customer. Thus, making corrections to the design or implementation is extremely costly in terms of customer satisfaction, and time as corrections to the design require the complete traversal of the design flow.
Consequently, there is a need in the art for a method and apparatus for verification of queue flow control that substantially covers the corner or worst case situations, and performs this verification early in the design flow. Although this would not completely eliminate the need for simulation, emulation, and/or verification, as there are some design aspects that must be handled in this fashion. However, by reducing the number of bugs, particularly the queue flow control bugs, early in the design flow results in a superior system design potentially a faster tune to market.